package com.echo.boot.structure.algorithm.sort.cmp.merge;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/4/22
 * Time: 17:15
 *
 * @author Administrator
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {9, 8, 2, 1, 4, 7, 10, 5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void sort(int[] arr) {
        int i = 0;
        int j = arr.length - 1;
        sort(arr, i, j);
    }

    static void sort(int[] arr, int i, int j) {
        if (i >= j) {
            return;
        }
        int mid = i + (j - i) / 2;
        sort(arr, i, mid);
        sort(arr, mid + 1, j);
        merge(arr, i, mid, j);
    }

    static void merge(int[] arr, int x, int mid, int y) {
        int[] assist = new int[y - x + 1];
        int k = 0;
        int i = x;
        int j = mid + 1;
        while (i <= mid && j <= y) {
            assist[k++] = arr[i] > arr[j] ? arr[j++] : arr[i++];
//            if(arr[i] > arr[j]){
//                assist[k] = arr[j];
//                k++;
//                j++;
//            }else{
//                assist[k] = arr[i];
//                k++;
//                i++;
//            }
        }
        while (i <= mid) {
            assist[k++] = arr[i++];
        }
        while (j <= y) {
            assist[k++] = arr[j++];
        }
//        System.out.println(Arrays.toString(assist));
        for (int l = 0; l < assist.length; l++) {
            arr[x + l] = assist[l];
        }
    }
}
